/*
 * Created on 3 Sep 2007
 *
 * Copyright (c) 2006 P.J.Leonard
 * 
 * http://www.frinika.com
 * 
 * This file is part of Frinika.
 * 
 * Frinika is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.

 * Frinika is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.

 * You should have received a copy of the GNU General Public License
 * along with Frinika; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 */

package model;

import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Vector;


import model.Board.Move;

public class BreadthFirstSearch implements Search {

	Board board;

	HashSet<Long> visited = new HashSet<Long>();

	public BreadthFirstSearch(Board board) {
		this.board = board;
	}

	/**
	 * start searching
	 */
	public int explore() {

		// parent less node with no move.
		Node root = new Node(null, null);

		int status;

		int depth = 0;   // start with a shallow search and get deeper
		do {
			status = exploreDepth(depth, root);  // explore to a given depth
			depth++;
		} while (status == UNKNOWN);  // keep on exploring till we find a solution.

		return status;

	}

	/**
	 * 
	 * @param depth
	 * @param node
	 * @return  WIN or FAIL or UNKNOWN
	 */
	private int exploreDepth(int depth, Node node) {

		// at depth 0 just expand the node
		if (depth == 0)	return expand(node);
		
		Iterator<Node> iter = node.children.iterator();

		while (iter.hasNext()) { // for all children

			Node child = iter.next();

			child.toMove.doMove();  // down a level 
			if (display) board.notifyObservers();
			// here we go recurively down.
			switch (exploreDepth(depth - 1, child)) {
			case WIN: return WIN;
			case FAIL:  // remove hopeless children
				iter.remove();
			}

			board.undo();   // back up a level
			if (display) board.notifyObservers();
		}

		if (node.children.size() == 0) // no children then fail.
			return FAIL;

		return UNKNOWN;

	}

	private int expand(Node node) {

		for (Board.Move move : board.getMoves()) {   // for all moves
			
			move.doMove();   // visit new state using move
			if (display) board.notifyObservers();
			
			if (board.hasWon())	return WIN;   // hooray 

			Long boardKey = board.longHashCode();
			
			if (!visited.contains(boardKey)) {  // ignore if already visited
				visited.add(boardKey);  // store state 
				node.addChild(move);    // add a child for current node.
			}

			board.undo();
			if (display) board.notifyObservers();
		}

		// if no children then this branch has failed.
		if (node.children.size() == 0) return FAIL;
		return UNKNOWN;
	
	}

	
	private class Node {
		Node parent;
		List<Node> children;
		Board.Move toMove; 		// move to get to this node 

		public Node(Node parent, Board.Move to) {
			this.parent = parent;
			this.toMove = to;
			children = new Vector<Node>();
		}

		public void addChild(Move move) {
			children.add(new Node(this, move));
		}

	}

}
